/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package tiralabra;

/**
 *
 * @author mebbeth
 */
public class Dkeko implements Keko {
    private KekoAlkio[] lista;
    private int loppu; /* osoittaa keon viimeistä alkiota seuraavaan paikkaan */

    public Dkeko(int koko) {
        lista = new KekoAlkio[koko];
        loppu = 0;
    }

    /*operaatiot */
    public void laitaKekoon (Ruutu[][] kartta, KekoAlkio alkio) {
        lista[loppu] = alkio;
        int temp = loppu; // viimeisen alkion indeksi
        KekoAlkio tempAlkio = lista[temp]; // otetaan väliaikaiseksi käsittelyssä oleva alkio
        short tempX = tempAlkio.annaX();
        short tempY = tempAlkio.annaY();
        int puolikas = (temp-1)/2; // lasketaan vanhemman indeksi
        KekoAlkio puolikasAlkio = lista[puolikas];
        short puolikasX = puolikasAlkio.annaX(); // haetaan vanhemman koordinaatit
        short puolikasY = puolikasAlkio.annaY();


        while(puolikas >= 0 /* katsotaan että tarkistus kulkee vain lopusta alkuun */
              && kartta[tempX][tempY].haeLyhin()  < kartta[puolikasX][puolikasY].haeLyhin()) {  // verrataan vanhempaan
            lista[temp] = puolikasAlkio;
            lista[puolikas] = tempAlkio; // alkiot vaihtavat paikkaa
            temp = puolikas;
            tempAlkio = lista[temp];
            tempX = tempAlkio.annaX();
            tempY = tempAlkio.annaY();

            puolikas = (temp-1)/2;
            puolikasAlkio = lista[puolikas];
            puolikasX = puolikasAlkio.annaX();
            puolikasY = puolikasAlkio.annaY();
        }
        // kun while on loppu
        loppu++;
    }

    public KekoAlkio otaPienin (Ruutu[][] kartta) {
        KekoAlkio lapsiVasen;
        KekoAlkio lapsiOikea;
        KekoAlkio tempAlkio;
        int vasen;
        int oikea;
        int temp;
        short vasenX;
        short vasenY;
        short oikeaX;
        short oikeaY;
        short tempX;
        short tempY;

        if (loppu < 1) { // jos keko on tyhjä
            return null;
        }
        /* debug
        short apux;
        short apuy;
        KekoAlkio apualkio;
        for (int i = 0; i<loppu;i++) {
            apualkio = lista[i];
            apux = apualkio.annaX();
            apuy = apualkio.annaY();
            System.out.println("i= "+i+" apux= "+apux+" apuy= "+apuy);

        }
        System.out.println();
        */
        
        KekoAlkio pienin = lista[0];
        lista[0] = lista[loppu-1]; // laitetaan keon päälle uusin alkio
        lista[loppu-1] = null; // tyhjennetään paikka heti
        loppu--;
        if (loppu == 1 || loppu == 0) {
            return pienin;       
        }
        tempAlkio = lista[0]; // ruvetaan päivittämään kekoehto uudelle
        tempX = tempAlkio.annaX();
        tempY = tempAlkio.annaY();
        temp = 0;
        if (loppu == 2) {
            // erikoistapaus sille, että keossa on enää 3 alkiota jäljellä, vertaillaan vanhempi ja lapsi
            lapsiVasen = lista[1]; // kekoalkio
            vasenX = lapsiVasen.annaX();
            vasenY = lapsiVasen.annaY();
            if (kartta[vasenX][vasenY].haeLyhin() < kartta[tempX][tempY].haeLyhin()) {
                lista[0] = lapsiVasen; // eli jäljelle jää kaksi, jos ovat väärässä järjestyksessä, vaihdetaan paikat
                lista[1] = tempAlkio;
            }
            return pienin;
        }
        vasen = (2*temp)+1; // lasketaan vasemman lapsen indeksi listalla
        oikea = (2*temp)+2; // sama oikealle lapselle
        lapsiVasen = lista[vasen];
        vasenX = lapsiVasen.annaX();
        vasenY = lapsiVasen.annaY();
        lapsiOikea = lista[oikea];
       // System.out.println("oikea = "+oikea);
        oikeaX = lapsiOikea.annaX();
        oikeaY = lapsiOikea.annaY();
        // loppu--; //koska poistettiin yksi, koko pienenee

        //kekoehdon ylläpito
        while(oikea < loppu /* eli ennen kuin osutaan alkioiden loppuun taulukossa */
                && (kartta[vasenX][vasenY].haeLyhin() < kartta[tempX][tempY].haeLyhin()
                || kartta[oikeaX][oikeaY].haeLyhin() < kartta[tempX][tempY].haeLyhin())) {
            if (kartta[vasenX][vasenY].haeLyhin() < kartta[oikeaX][oikeaY].haeLyhin()) {
                lista[vasen] = tempAlkio;
                lista[temp] = lapsiVasen;
                temp = vasen;
                // alkiot vaihtavat paikkaa keossa
            } else {
                lista[oikea] = tempAlkio;
                lista[temp] = lapsiOikea;
                temp = oikea; // päivitetään indeksi
            }
            tempAlkio = lista[temp]; // ruvetaan päivittämään kekoehto uudelle
            tempX = tempAlkio.annaX();
            tempY = tempAlkio.annaY();
            vasen = (2*temp)+1; // lasketaan vasemman lapsen indeksi listalla
            oikea = (2*temp)+2; // sama oikealle lapselle
            if (oikea >= loppu) {
                break; // Purukumilla me paikkaamme sen.
            }
            lapsiVasen = lista[vasen];
            /*System.out.println("vasen = "+vasen);
            System.out.println("oikea = "+oikea);
            System.out.println("temp = "+temp); DEBUG */
            vasenX = lapsiVasen.annaX();
            vasenY = lapsiVasen.annaY();
            lapsiOikea = lista[oikea];
            oikeaX = lapsiOikea.annaX();
            oikeaY = lapsiOikea.annaY();

        }
        return pienin;
    }
    public void korjaaAlkio (Ruutu[][] kartta, short X, short Y, int uusiMatka) {
        // ei mitään
    }


}
